<!DOCTYPE html>
<html>
	<head>
		<meta charset="UTF-8">
		<title></title>
	</head>
	<body>
		<script>
			function swap(arr, i, j) {
			    let temp = arr[i]
			    arr[i] = arr[j]
			    arr[j] = temp
			}

			function quickSort(arr, fromIndex, length) {
			    if (length < 2) {
			        return
			    }
			    let [firstIndexEqualPivot, lastIndexEqualPivot] = partition(arr, fromIndex, length)
			    // pivot 都已经排好序
			    quickSort(arr, fromIndex, firstIndexEqualPivot - fromIndex)
			    let subLength = fromIndex + length - 1 - (lastIndexEqualPivot + 1) + 1
			    // subLength =  末尾索引 - 第一个大于主元素的索引 + 1
			    quickSort(arr, lastIndexEqualPivot + 1, subLength)
			}
			
			function partition(arr, fromIndex, length) {
			    let lastIndex = fromIndex + length - 1
			    let randomIndex = fromIndex + Math.floor(Math.random() * length)
			    swap(arr, randomIndex, lastIndex)
			    let pivot = arr[lastIndex]
			    let lastIndexUnderPivot = fromIndex - 1
			    let firstIndexOverPivot = lastIndex
			    let currentLeftIndex = fromIndex
			    let currentRightIndex = lastIndex - 1
			    while (currentLeftIndex <= currentRightIndex) {
			        while (arr[currentLeftIndex] <= pivot) {
			            if (arr[currentLeftIndex] < pivot) {
			                swap(arr, lastIndexUnderPivot + 1, currentLeftIndex)
			                lastIndexUnderPivot++
			            }
			            currentLeftIndex++
			        }
			
			        while (arr[currentRightIndex] >= pivot) {
			            if (arr[currentRightIndex] > pivot) {
			                swap(arr, firstIndexOverPivot - 1, currentRightIndex)
			                firstIndexOverPivot--
			            }
			            currentRightIndex--
			        }
			        // 越界
			        if (currentLeftIndex > lastIndex - 1) {
			            break
			        }
			        // 越界
			        if (currentRightIndex < fromIndex) {
			            break
			        }
			        // 越界
			        if (currentLeftIndex > currentRightIndex) {
			            break
			        }
			        // 此时arr[currentLeftIndex] > pivot, arr[currentRightIndex] < pivot
			        swap(arr, currentLeftIndex, currentRightIndex)
			    }
			    swap(arr, firstIndexOverPivot, lastIndex)
			    let firstIndexEqualPivot = lastIndexUnderPivot + 1
			    let lastIndexEqualPivot = firstIndexOverPivot
			    return [firstIndexEqualPivot, lastIndexEqualPivot]
			}
			
			let arr = [1, 5, 2, 11, 7, 3, 1, 6, 17, 10]
			quickSort(arr, 0, arr.length)
			console.log(arr) // [ 1, 2, 3, 5, 6, 1, 7, 10, 11, 17 ]
		</script>
	</body>
</html>
